The broad context of this invention is in bridging the gap between implicit and explicit representations of surfaces. Explicit representations are most commonly used in Computer Graphics, because they are convenient for rendering and easily controlled by artists. They are defined by explicitly specifying where the surfaces lie, such as via parametric functions mapping a 2D domain onto a 3D surface. Implicit surfaces have advantages in contexts where surface topology changes rapidly and when it is desirable for nearby objects to merge in a soft way rather than with a hard cracks at the intersections. They are specified as the root of a scalar function defined over 3D space.
Level sets are a very useful representation of forms commonly used in a quickly developing sub-field of computational fluid dynamics. In addition to having the obvious scientific and engineering applications, these simulations have significant potential for simulating fluid phenomena such as water, smoke, mist and fire at resolutions sufficient for use in the computer graphics industry. Moving from a significant amount of hand animation and noise maps towards physically based simulations has the potential for creating increasingly realistic Computer Graphics and animations.
Form Representations used in Computer Graphics
There are many ways of explicitly representing geometric objects. Polygons, NURBS, and Subdivision Surfaces are commonly used in the graphics industry. It is common for objects modeled as these primitives to have imperfections such that they do not represent a perfectly enclosed volume with a well defined inside and outside. There may be holes or cracks in the surface, and the normals may be pointing in the wrong direction on parts of the surface. In order for the method of the present invention to be useful in practice, it should be able to produce a high quality level set representation of the surface from most commonly used explicit geometric models.
Explicit Representations
A detailed description of techniques for using these geometric object representations can be found in most modern comprehensive graphics textbooks such as (Watt A. & Watt, M. 1996).
Ray Trace Operator
There are many different representations one could use for efficient ray tracing of a geometry model. We give a description of how a BSP tree can be used for this purpose. Other alternative representations that met the necessary requirements of efficient ray tracing can be found in a modern computer graphics textbook such as (Watt A. & Watt, M. 1996). For example, a nested hierarchy of bounding boxes can be used to efficiently ray trace a NURBS surface set, and a combination of techniques might be combined to handle significantly varied and complex geometry.
Binary Space Partition Tree
A BSP tree is a method of representing a set of planar polygons such that the process of “ray casting” is efficient. It is a, preferably balanced, binary tree data structure in which each node is associated with a plane and a set of polygons that lie within that plane.
A BSP tree can be created in a recursive fashion from the root node on down to its leaves by applying this procedure for each node:
Choose a plane that is coplanar with one of the polygons in the face set. It is best to pick a plane that will “split” the face set evenly (see the next step) as such will allow for more efficient BSP tree traversals during “ray casting.”
Sort the set of faces into three new set: “in front”, “coplanar” and “behind.” A face whose vertices all lie within the chosen plane of the node will be placed in the “coplanar” set. A face whose vertices are all in front of the plane will be placed in the “in front” set. And a face whose vertices all lie behind the plane will be placed in the “behind” set. A face who's vertices lie both in front and behind the plane should be split into two faces, one who's vertices are completely in front of the plane and another who's vertices are completely behind the plane—these two newly created faces should then be placed into the “in front” set and the “behind” set respectively.
The “coplanar” set of faces is then associated with the current node. If the “in front” set of faces is not empty a “left-hand” child node should be created using the “in front” set as a starting point. The same logical also applies to the “behind” set and the “right-hand” child node.
Level Set
A comprehensive description of what is a level set and what can be done with one is given in the well-written textbook (Osher, S. & Fedkiw R. 2003.)
A level set is an n-dimensional scalar field which implicitly represents the interface between two regions in a domain. It represents such an interface as the zero-contour of the scalar field. A scalar field is defined mathematically by a function, φ(x), which associates a scalar value with each point in space. The zero contour of a scalar field (i.e. the interface represented by the level set), ┌, is the set of points in the domain whose image from applying φ is 0.
For the most part only 3D level sets are of real concern to us—although this method applies equally well in both 2D cases and in higher dimensional applications.
A level set also has the property that it is a signed distance field. This means that the magnitude of the scalar field at any point in the domain is the distance between that point and the nearest point on the interface. The sign of the scalar field function determines whether one is inside one region or the other—which sign denotes which region is arbitrary based on the chosen convention. The convention used in this document is for the interior of forms to have a positive sign.
Because of the limitations imposed by a finite computing architecture it is impossible to truly represent an arbitrary continuous scalar field over any unbounded domain. It is possible though to restrict the domain over which the scalar field is defined to a sub domain and then discretize the scalar field function within this sub domain into “voxels” of identical size within which the function result does not vary. For simplicity sake it is often convenient to restrict the sub domain to a quadrilateral (i.e. a 3D box.). FIG. 2 diagrams the voxel fields and associated terminology.
Each voxel of the discretized level set can now be represented by a single scalar. Conceptually the scalar associated with each voxel can be thought of as lying at its center. It is also not incorrect to view the scalars forming a uniform Cartesian grid over the sub domain of the now discretized level set.
                    Equation        ⁢                                  ⁢        1        ⁢                  :                ⁢                                  ⁢        Discretized        ⁢                                  ⁢        Level        ⁢                                  ⁢        Set                                          ϕ          ⁡                      (                          x              ⇀                        )                          =                  {                                                                                          ϕ                                          u                      ,                      U                                                        =                                                            T                                              w                        =                                                  >                          r                                                                                      ⁡                                          (                                              x                        ⇀                                            )                                                                                                                                        if                    ⁢                                                                                  ⁢                                          x                      ⇀                                                        ∈                  Ω                                                                                    undefined                                            otherwise                                                                            Equation        ⁢                                  ⁢        2        ⁢                  :                ⁢                                  ⁢        world        ⁢                  -                ⁢        to        ⁢                  -                ⁢        discrete        ⁢                                  ⁢        transform                                          T                      u            =                          >              w                                      ⁡                  (                      x            ⇀                    )                                                  u          x                =                  [                                                    x                x                            -                              w                x                                                    Δ              ⁢                                                          ⁢              c                                ]                                                  u          y                =                  [                                                    x                y                            -                              w                y                                                    Δ              ⁢                                                          ⁢              c                                ]                                                  u          z                =                  [                                                    x                z                            -                              w                z                                                    Δ              ⁢                                                          ⁢              c                                ]                                        Equation        ⁢                                  ⁢        3        ⁢                  :                ⁢                                  ⁢        discrete        ⁢                  -                ⁢        to        ⁢                  -                ⁢        world        ⁢                                  ⁢        transform                                          T                      u            ->            w                          ⁡                  (                      x            _                    )                                                  x          x                =                              w            x                    +                                    u              x                        ⁢                                                  ⁢            Δ            ⁢                                                  ⁢            c                                                            x          y                =                              w            y                    +                                    u              y                        ⁢            Δ            ⁢                                                  ⁢            c                                                            x          z                =                              w            z                    +                                    u              z                        ⁢            Δ            ⁢                                                  ⁢            c                              A minimalist level set data structure could consist simply of:    1. A vector represent the minimum extent of the level set's defined region of validity, w[min].    2. The dimensions of the level set in cubes/voxels: w, h, d    3. The side length of the cubes: Δc    4. The set of scalar values, each associated with a particle voxel of the level set: ψ(u)ψu∈, u∈ℑEquation 4: definition of ψTr→i(u)i=ux+uy·w+uz·w·hEquation 5: Discrete-to-ψ-index transformationExisting Mesh to Level Set Methods
There are three general approaches common in the literature for converting explicit surface representations into volumetric distance field representations: closest point, narrow band initialization with Eikonal extension, and full volume rasterization.
Closest point approaches to conversion tend to iterate over all or a subset of the voxels in a volume instead of iterating over the surfaces of the input mesh. Examples include [Payne and Toga 1992]. For each voxel the closest point on the explicit representation is calculated and the distance along with the relative direction of the surface normal at this location is used to set the voxel value. The more efficient closest point algorithms areO(logF). If one initializes the whole volume using this approach the efficiency is O(n3 logF). Narrow band initialization methods of converting meshes into level set focus on initializing the band of voxels immediate adjacent to the surface of the mesh to their correct values and then using this interface as the boundary condition of an Eikonal equation solver such that the solution can be extended throughout the volume (as described in [Sethian 1996]). One method to initialize the narrow band is through the 3D rasterization of the polygons composing the mesh in an analogous manner to how 2D polygons are rendered to a frame buffer. Sometimes the 3D rasterization is done such that the initial narrow band is initialized to subvoxel distance values, These approaches generally require O(F+n3) computations. [Breen et al. 1998], [Betelu et al. 2001].
Recently a full volume rasterization method, [Mauch 2000], has achieved xcellent efficiency, O(n3), by using polyhedral volumes extended from the input mesh surfaces to initialize into a correct distance field via rasterization large sections of the volume at once. The research with the most similarity to ours is work done by [Yngve and Turk 2002]. Yngve and Turk make use of a process of axis aligned ray casting in order to convert a mesh into an anti-aliased binary volume which in turn is converted into a signed distance field via a 3D Eikonal solver. The whole of this conversion process requires O(n3+n2 log f) computations assuming the fastest method are used.